package os.homework5;

import java.util.*;

public class BuddySystem {
    //当前系统容量为1024K,最小的分区32K
    static int free= 1024;//整个可分配内存的大小

    public static List<int[]> size1024=new LinkedList<>();
    public static List<int[]> size512=new LinkedList<>();
    public static List<int[]> size256=new LinkedList<>();
    public static List<int[]> size128=new LinkedList<>();
    public static List<int[]> size64=new LinkedList<>();
    public static List<int[]> size32=new LinkedList<>();

    //用来存放所有的空闲分区双向链表
    public static Map<Integer, List> freeMap=new HashMap<Integer, List>();

    //初始化所有空闲分区链表
    public static void init_freeList(){
        //一开始内存空间的大小,是一整块的1024K连续内存
        int c[]=new int[1024];
        for(int i=0;i<1024;++i){
            c[i]='*';
        }
        size1024.add(c);


        freeMap.put(1024,size1024);
        freeMap.put(512,size512);
        freeMap.put(256,size256);
        freeMap.put(128,size128);
        freeMap.put(64,size64);
        freeMap.put(32,size32);
    }

    //假设一个进程申请 67K的内存
    public static boolean requestMemory(int requestMem){
        //index表示Map中空闲分区链表的容量的2^p
        int p;
        //不能大于最大空闲分区
        if(requestMem>1024){
            System.out.println("请求内存大于系统的空闲内存，申请失败");
            return false;
        }
        //计算p的值
        p= (int) Math.ceil(Math.log(requestMem)/Math.log(2));
        //如果小于最小分区，则按最小分区分配
        if(p<5){
            p=5;//2^5=32
        }
        //取出对应的空闲分区链表
        List<int[]> tempSizeList= freeMap.get((int)Math .pow(2,p));
        //如果列表为空，需要向上取更大的空闲分区，分割伙伴系统
        if(tempSizeList.size()==0){
            boolean flag=breakMemory((int)Math.pow(2,p+1));
            if(flag==false){
                System.out.println("return false;//分割失败，返回false");
                return false;//分割失败，返回false
            }
        }
        //取出一个2^p大小的空闲分区
        int c[]=getSizeList((int)Math.pow(2,p));
        //输出使用的内存
        System.out.println("此次请求了 "+requestMem+" 的内存");

        return true;
    }


    //取出内存块
    private static int[] getSizeList(int size) {
        int[] a=new int[2];
        List<int[]>temp=freeMap.get(size);//取出size大小的空闲分区链表
        if(temp.size()>0){//链表不空
            a=temp.get(0);//取出第一块
            temp.remove(0);//删除取出的第一块
            freeMap.put(size,temp);//放回Map中
        }
        return a;
    }
    //分割页面
    private static boolean breakMemory(int size) {

        if(size>1024){
            return false;
        }
        //取出对应的空闲分区链表
        List<int[]> tempSizeList= freeMap.get(size);
        boolean flag=true;
        //如果列表为空，需要向上取更大的空闲分区，分割伙伴系统
        if(tempSizeList.size()==0){
            System.out.println("需要向上取更大的空闲分区，分割伙伴系统  当前size="+size);
            flag=breakMemory(size*2);
        }
        //获得可分割的内存块，执行分割
        if(flag==true){
            System.out.printf("对%4d 大小的内存块分割成功啦   ",size);
            //取出空闲可用的内存链表
            tempSizeList=freeMap.get(size);
            //取出空闲可用的内存
            int[] c=tempSizeList.get(0);
            //将其移除
            tempSizeList.remove(0);
            freeMap.put(size,tempSizeList);

            //分割
            int[] midC=new int[2];
            midC[0]=c[0];
            midC[1]=midC[0]+(size/2-1);
            c[0]=midC[0]+1;

            List<int[]> tem = freeMap.get(size / 2);//得到size/2大小的页的列表
            tem.add(c);//将分割好的两个页插入进去
            tem.add(midC);
            freeMap.put(size / 2, tem);
//            System.out.println("前一块内存地址"+c+"  后一块地址"+midC);
            return true;
        }
        else{
            //如果更大的空闲链表块分割失败，那就真的失败了
            System.out.println(size+"如果更大的空闲链表块分割失败，那就真的失败了");
            return false;
        }
    }

    public static void main(String[] args) {
        init_freeList();
        Scanner scanner=new Scanner(System.in);
        int requestMem=67;//申请的存储空间长度
        while (scanner.hasNext()){
            requestMem= scanner.nextInt();
            System.out.println("请求申请"+requestMem+"K的内存");
            requestMemory(requestMem);
        }

    }
}
